#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 977. 有序数组的平方.py
@time: 2022/2/28 20:05
@desc: https://leetcode-cn.com/problems/squares-of-a-sorted-array/
> 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

1. 根据单调性，分成两个部分，然后归并
2.
'''
class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        idx = 0
        while idx<n and nums[idx] < 0:
            idx += 1
        # 全都是负数
        if idx == n or idx == 0:
            for i in range(n):
                nums[i] = nums[i] ** 2
            if idx == n: return nums[::-1]
            if idx == 0: return nums
        for i in range(n):
            nums[i] = nums[i]**2
        ans = [0]*(n)
        nums[:idx] = nums[idx-1::-1]
        i, j, k = 0, idx, 0
        while i<idx and j<n:
            if nums[i]<nums[j]:
                ans[k] = nums[i]
                i += 1
            else:
                ans[k] = nums[j]
                j += 1
            k += 1
        while i<idx:
            ans[k] = nums[i]
            i += 1
            k += 1
        while j<n:
            ans[k] = nums[j]
            j += 1
            k += 1
        return ans

if __name__ == '__main__':
    ans = Solution().sortedSquares([-1, -1, -1])
    print(ans)
